// cracking coding interveiw
// Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n-pair of parenthesis
// Example:
//	Input: 3
//	Output: ((())), (()()), (())(), ()(()), ()()()
// 12:10PM-12:22PM(lunch break)

#include<set>
#include<string>
#include<iostream>
#include<map>
#include<utility>
using namespace std;

void validbraket(int n, set<string>& str, map<int, set<string> > &mem) {
	map<int, set<string> >::iterator mapiter=mem.find(n);
	if(mapiter !=mem.end()) {
		str=mapiter->second;
		return;
	}
	if(n<0) {
		exit(-1);
	}
	if(n==0) {
		str.clear();
		str.insert("");
		mem.insert(make_pair(n, str));
		return;
	}

	str.clear();
	for(int i=0; i<n; i++) {
		set<string> str1, str2;
		set<string>::iterator iter1, iter2;
		validbraket(i, str1, mem);
		validbraket(n-1-i, str2, mem);
		for(iter1=str1.begin(); iter1 != str1.end(); iter1++) {
			for(iter2=str2.begin(); iter2 != str2.end(); iter2++) {
				string tmp="("+*iter1+")"+*iter2;
				str.insert(tmp);
			}
		}
	}
	mem.insert(make_pair(n, str));
}

int main() {
	set<string> str;
	map<int, set<string> > mem;
	validbraket(3, str, mem);
	return 0;
}